Search results for " Recursion"
showing 7 items of 7 documents
When can an equational simple graph be generated by hyperedge replacement?
1998
Infinite hypergraphs with sources arise as the canonical solutions of certain systems of recursive equations written with operations on hypergraphs. There are basically two different sets of such operations known from the literature, HR and VR. VR is strictly more powerful than HR on simple hypergraphs. Necessary conditions are known ensuring that a VR-equational simple hypergraph is also HR-equational. We prove that two of them, namely having finite tree-width or not containing the infinite bipartite graph, are also sufficient. This shows that equational hypergraphs behave like context-free sets of finite hypergraphs.
MR 2944715 Reviewed Zhu S. On the recursion formula for double Hurwitz numbers. Proceedings of the American Mathematical Society (2012) 140, no. 11, …
2013
Let $\mu = (\mu_{1}, \mu_{2}, \ldots, \mu_{m})$ and $\nu = (\nu_{1}, \nu_{2}, \ldots, \nu_{n})$ be two partitions of a positive integer $d$. In this paper, the author considers degree $d$ branched coverings of $\mathbb{P}^{1}$ with at most two special points, $0$ and $\infty$. Specifically, the purpose of the author is to give a recursion formula for double Hurwitz numbers $H^{g}_{\mu, \nu}$ by the cut-join analysis. Here, $H^{g}_{\mu, \nu}$ denotes the number of genus $g$ branched covers of $\mathbb{P}^{1}$ with branching date corresponding to $\mu$ and $\nu$ over $0$ and $\infty$, respectively. Furthemore, as application, the author gets a polynomial identity for linear Goulden-Jackson-Va…
Introduction
2017
The book is devoted to three key questions concerning the relationship between complexity and natural language. Briefly, such questions are: (a) What kind of complexity for natural language? (b) Which theory of language in the perspective of complexity? (c) What sorts of methods and models in the analysis of the observed phenomena? All the essays in this volume show the reference to complexity as a constant element. However, the use of the singular may not be entirely appropriate.
Le métier de linguiste.
2021
The paper aims to analyze the epistemological status of theoretical linguistics.
Is recursion language-specific? Evidence of recursive mechanisms in the structure of intentional action
2014
In their 2002 seminal paper Hauser, Chomsky and Fitch hypothesize that recursion is the only human-specific and language-specific mechanism of the faculty of language. While debate focused primarily on the meaning of recursion in the hypothesis and on the human-specific and syntax-specific character of recursion, the present work focuses on the claim that recursion is language-specific. We argue that there are recursive structures in the domain of motor intentionality by way of extending John R. Searle's analysis of intentional action. We then discuss evidence from cognitive science and neuroscience supporting the claim that motor-intentional recursion is language-independent and suggest so…
Verification of Well-Formed Communicating Recursive State Machines
2008
AbstractIn this paper we introduce a new (non-Turing equivalent) formal model of recursive concurrent programs called well-formed communicating recursive state machines (CRSM). CRSM extend recursive state machines (RSM) by allowing a restricted form of concurrency: a state of a module can be refined into a finite collection of modules (working in parallel) in a potentially recursive manner. Communication is only possible between the activations of modules invoked on the same fork. We study the model-checking problem of CRSM with respect to specifications expressed in a temporal logic that extends CaRet with a parallel operator (ConCaRet). We propose a decision algorithm that runs in time ex…
On the impact of forgetting on learning machines
1995
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For technical reasons, it was necessary to consider two types of memory : long and sh…